#include "../../tools.h"
#include <cstring>              

class Solution {
public:
            int uniquePaths(int m, int n) {
                int dp[m + 1][n + 1];
                memset(dp, 0, (m + 1) * (n + 1) * sizeof(int));
                dp[m - 1][n - 1] = 1;

                // for(int i = 0; i < m; ++i){
                //     for(int j = 0; j < n; ++j)
                //         cout << dp[i][j] << " ";
                //     cout << endl;
                // }

                // show(dp);
                for(int j = n - 2; j > -1; --j)
                    dp[m - 1][j] = dp[m - 1][j + 1] + dp[m][j];

                for(int i = m - 2; i > -1; --i){
                    for(int j = n - 1; j > -1; --j){
                        dp[i][j] = dp[i][j + 1] + dp[i + 1][j];
                    }
                }
                return dp[0][0];
            }
};

int main(int argc, char const *argv[])
{
    Solution s;

    cout << s.uniquePaths(3, 7);
    
    return 0;
}
